package main

import (
	"fmt"
	"reflect"
)

// 链表
// 只用 Next 时, 表示单向链表
// 当使用 Pre 时, 表示双向链表
type Link struct {
	Key   interface{}
	Value interface{}
	Next  *Link
	Pre   *Link
}


// 使用链表实现堆栈， 堆栈是filo
type Stack struct{
	Head *Link
}

func NewStack()*Stack{
	var queue = new(Stack)
	queue.Head = new(Link)
	queue.Head.Next = nil
	return queue
}

func (q *Stack) Push(m *Link){
	m.Next = q.Head.Next
	q.Head.Next  = m
}

func (q *Stack) Pop()*Link{
	m := q.Head.Next
	q.Head.Next = m.Next
	m.Next = nil
	return m
}

func (q *Stack)String()string{
	t := q.Head.Next
	str := "head.next-> "
	for t != nil {
		str += fmt.Sprintf(" (%v, %p)-> ",t.Value , t.Next)
		t = t.Next
	}
	return str
}


// 使用链表实现  队列是一个先进先出，fifo
type Queue struct{
	Head *Link
	Tail *Link
}

func NewQueue()*Queue{
	q := new(Queue)
	q.Head = new(Link)
	q.Tail = new(Link)
	q.Head.Next = nil
	q.Tail.Next = q.Head.Next
	return q
}

func (q *Queue)Push(m *Link){
	if q.Head.Next == nil {
		q.Head.Next = m
	}
	if q.Tail.Next == nil {
		q.Tail.Next = m
	}else{
		q.Tail.Next.Next = m 
		q.Tail.Next = m
	} 
}

func (q *Queue)Pop()*Link{
	t := q.Head.Next
	q.Head.Next = t.Next
	t.Next = nil
	return t
}

func (q *Queue)String()string{
	t := q.Head.Next
	str := "head.next-> "
	for t != nil {
		str += fmt.Sprintf(" (%v, %p)-> ",t.Value , t.Next)
		t = t.Next
	}
	return str + " <- Tail.next"
}

// 双向链表的操作
type LRU struct {
	Head *Link
	Tail *Link
	Cache int
}

func NewLink(key , value interface{})*Link{
	dl := new(Link)
	dl.Key = key
	dl.Value = value
	dl.Next = nil
	dl.Pre = nil
	return dl
}

func NewLRU(Cache int)*LRU{
	lru := new(LRU)
	lru.Cache = Cache
	lru.Head = NewLink("Head","head->")
	lru.Tail = NewLink("Tail","Tail->")
	return lru

}
func (l *LRU)Set(src *Link){
	defer fmt.Println("set ",l)
	if l.Cache <= 0 {
		l.Pop()
	}
	src.Next = l.Head.Next
	if l.Head.Next != nil {
		l.Head.Next.Pre = src
	}
	l.Head.Next = src
	if l.Tail.Next == nil {
		l.Tail.Next = src
	}
	l.Cache --
}

func (l *LRU)Pop()*Link{
	t := l.Tail.Next
	l.Tail.Next = l.Tail.Next.Pre
	l.Tail.Next.Next = nil
	t.Pre = nil
	l.Cache ++
	return t
}

func (l *LRU)MoveToHead(key interface{})interface{}{
	if l.Head.Next == nil {
		return -1
	}
	if reflect.DeepEqual(l.Head.Next.Key, key) {
		return l.Head.Next.Value
	}
	cur := l.Head.Next.Next
	for cur != nil {
		if reflect.DeepEqual(cur.Key, key) {
			cur.Pre.Next = cur.Next
			if cur.Next != nil {
				cur.Next.Pre = cur.Pre
			}else{
				l.Tail.Next = cur.Pre
			}
			cur.Pre = nil
			cur.Next = l.Head.Next
			l.Head.Next.Pre = cur
			l.Head.Next = cur
			return cur.Value
		}
		cur = cur.Next
	}
	return -1
}

func (l *LRU)Get(key interface{})interface{}{
	defer fmt.Println("get ",l )
	return l.MoveToHead(key)
}

func (l *LRU)String()string{
	t := l.Head.Next
	str := "head.next-> "
	for t != nil {
		str += fmt.Sprintf(" <-pre[(%p,%p,%p)(%v,%v,%v)]]next-> ",t.Pre,t, t.Next, t.Key, t.Value , l.Cache)
		t = t.Next
	}
	return str + " <-Tail.next"
}

func LRUCache( operators [][]int ,  k int ) []interface{} {
    // write code here
    ana := make([]interface{}, 0, 10)
    queue := NewLRU(k)
    for _, data := range operators {
        switch data[0] {
            case 1 :
            queue.Set(NewLink(data[1],data[2]))
            case 2 :
            ana = append(ana, queue.Get(data[1]))
        }
    }
    return ana
}
